package easy;

/**
 * 实现 strStr() 函数。 
 * 
 *  给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如
 * 果不存在，则返回 -1 。
 *  说明：
 *  当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
 *  对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。 
 *
 *  示例 1：
 * 输入：haystack = "hello", needle = "ll"
 * 输出：2
 *
 *  示例 2：
 * 输入：haystack = "aaaaa", needle = "bba"
 * 输出：-1
 *
 *  示例 3：
 * 输入：haystack = "", needle = ""
 * 输出：0
 *
 *  提示：
 *  0 <= haystack.length, needle.length <= 5 * 104 
 *  haystack 和 needle 仅由小写英文字符组成 
 *  
 *  Related Topics 双指针 字符串 字符串匹配 
 *  👍 1044 👎 0
 */
public class L28_实现strStr {
    public static void main(String[] args) {
        int res = new L28_实现strStr().strStr("abc","c");
        System.out.println(res);
    }

    /**
     * 暴力解法.
     *
     * 执行耗时:404 ms,击败了38.36% 的Java用户
     * 内存消耗:38.8 MB,击败了11.92% 的Java用户
     */
    public int strStr(String haystack, String needle) {
        int len1 = haystack.length();
        int len2 = needle.length();

        if (len1 < len2) {
            return -1;
        }
        if (len1 == len2){
            return haystack.equals(needle) ? 0 : -1;
        }

        for (int i = 0; i < len1 - len2 + 1; i++) {
            String tmp = haystack.substring(i, i+len2);
            if (tmp.equals(needle)){
                return i;
            }
        }
        return -1;
    }

    public int strStr2(String haystack, String needle){
        return 0; //todo
    }
}
